package alo;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @ClassName t10
 * @Description TODO
 * @Author Fanxc
 * @DATE 2021/4/20 21:12
 * @Version 1.0
 */
public class t10 {

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    public ArrayList<ArrayList<Integer>> zigzagLevelOrder (TreeNode root) {
        ArrayList<ArrayList<Integer>> lists=new ArrayList<>();
        Queue<TreeNode> queue=new LinkedList<>();
        if (root==null)return lists;
        queue.offer(root);
        while (!queue.isEmpty()){
            ArrayList<Integer> list=new ArrayList<>();
            for(int i= queue.size();i>0;i--){
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left!=null) queue.offer(node.left);
                if (node.right!=null) queue.offer(node.right);
            }
            if (lists.size()%2==1) Collections.reverse(list);
            lists.add(list);
        }
        return lists;
    }
}
